#ifndef TREE
#define TREE

#include <string>

#define NOTFOUND -1

using namespace std;

class LessonList;
class Lesson;
class Node;
class InnerNode;
class Leaf;
class Tree_2_4;

class Object
{
	protected:
		int count;
	public:
		Object() { count = 0; }
};

class Lesson
{
	private:
		Lesson *nextLesson;
		int grade;
		string courseId, courseName;
	public:
		Lesson() {};
		Lesson ( const Lesson &lesson );
		Lesson ( string courseId, string courseName, int grade );
		Lesson *Next() { return nextLesson; }
		void SetNext ( Lesson *lesson ) { nextLesson = lesson; }
		void Print();
		string CourseId() { return courseId; }
};

class LessonList : public Object
{
	private:
		Lesson *start;
	public:
		LessonList();
		~LessonList();
		void AddLesson ( Lesson newLesson );
		bool Empty() { return count == 0 ? true : false; }
		void Print ();
		void Delete ( string courseId );
};

class Node : public Object
{
	friend class Tree_2_4;
	protected:
		int studentIds[4];
		Object *pointers[4];
		InnerNode *parent;
		Tree_2_4 *tree;
		bool isLeaf;
	public:
		Node( InnerNode *parent, Tree_2_4 *tree , bool leaf );
		Node *Pointer ( int i );
		int Count() { return count; }
		bool Has ( int studentId );
		int Max() { return studentIds[count - 1]; }
		bool IsFull() { return count == 4 ? true : false; }
		virtual void Insert ( int studentId, Lesson data ) { };
		void SetParent ( InnerNode *parent ) { this->parent = parent; }
		void Print();
		int Find ( int studentId );
		int Find ( Object *object );
		Object *GetPointer ( int studentId );
		int GetPointer ( Object * );
		bool CanGive ( void ) { return count > 2; }
		bool SiblingCanGive ( void );
		void TakeFromSibling ( int studentId );
		Node *GetSibling ( void );
		void Delete ( int studentId );
		void Merge ( int studentId );
		bool HasParent ( void ) { return parent != NULL; }
		virtual bool IsLeaf ( void ) { return false; }  
};

class InnerNode : public Node
{
	private:
		void Split ( InnerNode *newNode, int studentId, Node *pointer);
	public:
		InnerNode ( InnerNode *parent , Tree_2_4 *tree) : Node ( parent , tree, false ){};
		InnerNode ( InnerNode *parent, Node *leftPointer, int leftId, Node *rightPointer, int rightId, Tree_2_4 *tree );
		void Insert ( int studentId, Lesson data );
		void Insert ( int studentId, Node *pointer );
		void UpdateChildrenParent ( void );
		void UpdateSeparator ( Object *child, int studentId );
		InnerNode *Next ( void );
		bool IsLeaf ( void ) { return false;}  
};

class Leaf : public Node
{
	friend class Tree_2_4;
	private:
		Leaf *next;
		int FindStudent ( int studentId );
		void Split (  Leaf *newNode, int studentId, Lesson lesson);
	public:
		Leaf ( InnerNode *parent, Tree_2_4 *tree);
		bool HasNext ( void ) { return next != NULL; }
		void Insert ( int studentId, Lesson data );
		void SetNext ( Leaf *nextLeaf ) { next = nextLeaf; } 
		LessonList *GetLessonList ( int studentId );
		void RangePrint ( int from, int to );
		bool HasParent ( void ) { return parent != NULL; }
		bool IsLeaf ( void ) { return true ;}  
};

class Tree_2_4
{
	private:
		Node *root;
		Leaf *firstLeaf;
		int height;
		int count;
		LessonList *Find ( int studentId );
		Leaf *FindLeaf ( int studentId );
		friend class Node;
		friend class InnerNode;
		friend class Leaf;
		Leaf *GetPrevious ( Leaf *leaf);
		void NewRoot ( Node *leftPointer, int leftId, Node *rightPointer, int rightId, bool leaf = false );
		void NewStudentId() { count++; }
	public:
		Tree_2_4 ( void );
		~Tree_2_4 ( void ); 
		bool Empty() { return count == 0 ? true : false; }
		void Insert ( int studentId, string courseId, string courseName, int grade );
		void Print();
		void PrintLessons ( int studentId );
		void RangeFind ( int from, int to );
		void Delete ( int studentId, string courseId );
		void Delete ( int studentId );
};

#endif
